#include<iostream>
#include<vector>
#include<algorithm>

//https://leetcode.cn/problems/valid-triangle-number/
using namespace std;
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int left, right, c;
        left = 0, right = nums.size() - 2, c = nums.size() - 1;
        int cnt = 0;
        while (c > 1) {
            while (left < right) {
                if (nums[left] + nums[right] > nums[c]) {
                    cnt += right - left;
                    right--;
                }
                else {
                    left++;
                }
            }
            c--;
            left = 0;
            right = c - 1;
        }
        return cnt;
    }
};

int main()
{
    vector<int> v = { 2,2,3,4,5,7,8,9 };
    int n=Solution().triangleNumber(v);
    cout << n;
    return 0;
}